﻿using System.Diagnostics;
using System.Text;

namespace DataStructure;

//保留数组队列
public class RsvSeqListQueue<E> : IQueue<E>
{
    //保留数组作为底层的数据结构
    private RsvSeqList<E> list;

    //获取队列元素的个数 O（1）
    public int Count => list.Count;

    //查看队列是否为空 O（1）
    public bool IsEmpty => list.IsEmpty;

    //创建容量为capacity的队列
    public RsvSeqListQueue(int capacity)
    {
        list = new RsvSeqList<E>(capacity);Stack<int> ints = new Stack<int>(capacity);
    }

    //使用默认的容量创建队列
    public RsvSeqListQueue()
    {
        list = new RsvSeqList<E>();
    }

    //入队。往队尾添加元素 O（1）
    public void Enqueue(E e)
    {
        list.AddLast(e);
    }

    //出队。删除队首的元素, 底层数组只做逻辑上删除 O（1）
    public E Dequeue()
    {
        return list.RemoveFirst();
    }

    //查看队首的元素 O（1）
    public E Peek()
    {
        return list.GetFirst();
    }

    //清空队列
    public void Clear()
    {
        list.Clear();
    }

    //打印数组队列信息
    public override string ToString()
    {
        StringBuilder res = new StringBuilder(list.ToString());
        res.Replace("[", "front [");

        return "Queue: " + res.ToString() + " tail";
    }
}

class RsvSeqListQueue
{
    static void Main(string[] args)
    {
        ///*
        RsvSeqListQueue<int> rsvSeqListQueue= new RsvSeqListQueue<int>();
        for (int i = 0; i < 20; i++)
        {
            rsvSeqListQueue.Enqueue(i);
            Console.WriteLine(rsvSeqListQueue);
        }

        rsvSeqListQueue.Dequeue();
        rsvSeqListQueue.Dequeue();
        Console.WriteLine(rsvSeqListQueue);


        Console.Read();
        //*/

        /*
        //计算数组队列和循环队列执行N次入队和出队操作的运行时间
        //对于TestQueue方法：
        //数组队列为O(n^2)  运行时间和数据规模的增长成平方倍的关系 
        //循环队列为O(n）  运行时间和数据规模的增长成正比关系
        int N = 20000;

        //数组队列
        SeqListQueue<int> seqListQueue = new SeqListQueue<int>();
        long t1 = TestQueue(seqListQueue, N);
        Console.WriteLine("SeqListQueue'time: " + t1 + "ms");

        //循环队列
        CirSeqListQueue<int> cirSeqListQueue = new CirSeqListQueue<int>();
        long t2 = TestQueue(cirSeqListQueue, N);
        Console.WriteLine("CirSeqListQueue'time: " + t2 + "ms");

        //保留队列
        RsvSeqListQueue<int> rsvSeqListQueue = new RsvSeqListQueue<int>();
        long t3 = TestQueue(rsvSeqListQueue, N);
        Console.WriteLine("RsvSeqListQueue'time: " + t3 + "ms");

        //C#自带的循环队列
        Queue<int> queue = new Queue<int>();
        Stopwatch t = new();
        t.Start();

        for (int i = 0; i < N; i++)
            queue.Enqueue(i);
        for (int i = 0; i < N; i++)
            queue.Dequeue();

        t.Stop();
        Console.WriteLine("Queue'time: " + t.ElapsedMilliseconds + "ms");

        Console.Read();
        */
    }

    static long TestQueue(IQueue<int> queue, int n)
    {
        Stopwatch t = new();
        t.Start();

        for (int i = 0; i < n; i++)
            queue.Enqueue(i);
        for (int i = 0; i < n; i++)
            queue.Dequeue();
        t.Stop();
        return t.ElapsedMilliseconds;
    }
}
